package com.ssh;

public class AddTwoNumbers_2 {
	
	public static void main(String[] args) {
		ListNode l1 = new ListNode(8);
		ListNode l2 = new ListNode(9);
		ListNode l3 = new ListNode(9);
		ListNode l4 = new ListNode(2);
		ListNode l5 = new ListNode(6);
		ListNode l6 = new ListNode(4);
		l1.next = l2;
		l2.next = l3;
		/*
		l4.next = l5;
		l5.next = l6;*/
		
		ListNode l = addTwoNumbers(l1, l4);
		while (l.next != null) {
			System.out.println(l.val);
			l = l.next;
		}
		System.out.println(l.val);
	}
	
	/**
	 * 链式加法，控制进位
	 * 注意：进位位的值，下一个结点是否为空，两个链表的的长度需要注意
	 * @param l1
	 * @param l2
	 * @return
	 */
	public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		int z = 0;
		int t = 0;
		ListNode lz = new ListNode(0);
		ListNode l;
		l = lz;
		t = l1.val + l2.val;
		if (t >= 10) {
			z = 1;
			l.val = t % 10;
		}else {
			l.val = t;
		}
        while(l1.next!=null || l2.next != null || z == 1) {
        	if (l1.next!=null && l2.next!=null) {
        		l1 = l1.next;
            	l2 = l2.next;
        		t = l1.val + l2.val + z;
        		if (t >= 10) {
        			z = 1;
        			ListNode x = new ListNode(t % 10);
        			l.next = x;
        			l = l.next;
        		}else {
        			ListNode x = new ListNode(t);
        			l.next = x;
        			l = l.next;
        			z = 0;
        		}
        	}else if (l1.next!=null && l2.next==null) {
        		l1 = l1.next;
        		if (z == 1) {
        			t = l1.val + z;
            		if (t >= 10) {
            			z = 1;
            			ListNode x = new ListNode(t % 10);
            			l.next = x;
            			l = l.next;
            		}else {
            			ListNode x = new ListNode(t);
            			l.next = x;
            			l = l.next;
            			z = 0;
            		}
        		}else {
        			ListNode x = new ListNode(l1.val + z);
        			l.next = x;
        			l = l.next;
        		}
        	}else if (l1.next==null && l2.next!=null) {
            	l2 = l2.next;
        		if (z == 1) {
        			t =l2.val + z;
            		if (t >= 10) {
            			z = 1;
            			ListNode x = new ListNode(t % 10);
            			l.next = x;
            			l = l.next;
            		}else {
            			ListNode x = new ListNode(t);
            			l.next = x;
            			l = l.next;
            			z = 0;
            		}
        		}else {
        			ListNode x = new ListNode(l2.val + z);
        			l.next = x;
        			l = l.next;
        		}
        	}else if (l1.next==null && l2.next==null) {
	        	if (z == 1) {
	        		ListNode x = new ListNode(z);
	    			l.next = x;
	    			l = l.next;
	    			z = 0;
	        	}
        	}
        }
        l = lz;
        return l;
    }
}
class ListNode {
     int val;
     ListNode next;
     ListNode(int x) { 
    	 val = x;
     }
}
